{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Magnetic Force Between Two Balls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两球之间的磁力"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有&nbsp;<code>n</code>&nbsp;个空的篮子，第&nbsp;<code>i</code>&nbsp;个篮子的位置在&nbsp;<code>position[i]</code>&nbsp;，Morty&nbsp;想把&nbsp;<code>m</code>&nbsp;个球放到这些篮子里，使得任意两球间&nbsp;<strong>最小磁力</strong>&nbsp;最大。</p>\n",
    "\n",
    "<p>已知两个球如果分别位于&nbsp;<code>x</code>&nbsp;和&nbsp;<code>y</code>&nbsp;，那么它们之间的磁力为&nbsp;<code>|x - y|</code>&nbsp;。</p>\n",
    "\n",
    "<p>给你一个整数数组&nbsp;<code>position</code>&nbsp;和一个整数&nbsp;<code>m</code>&nbsp;，请你返回最大化的最小磁力。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/16/q3v1.jpg\" style=\"height: 195px; width: 562px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>position = [1,2,3,4,7], m = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>将 3 个球分别放入位于 1，4 和 7 的三个篮子，两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>position = [5,4,3,2,1,1000000000], m = 2\n",
    "<strong>输出：</strong>999999999\n",
    "<strong>解释：</strong>我们使用位于 1 和 1000000000 的篮子时最小磁力最大。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == position.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= position[i] &lt;= 10^9</code></li>\n",
    "\t<li>所有&nbsp;<code>position</code>&nbsp;中的整数 <strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li><code>2 &lt;= m &lt;= position.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [magnetic-force-between-two-balls](https://leetcode.cn/problems/magnetic-force-between-two-balls/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [magnetic-force-between-two-balls](https://leetcode.cn/problems/magnetic-force-between-two-balls/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,7]\\n3', '[5,4,3,2,1,1000000000]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        n = len(position)\n",
    "        all_sum = sum(position)\n",
    "        for i in range(n-1,0, -1):\n",
    "            position[i] = position[i]-position[i-1]\n",
    "        min_offset = min(position[1:])\n",
    "        m -= 1\n",
    "\n",
    "        # print(offset_list, m)\n",
    "        def calculate(target):\n",
    "            cur_force = 0\n",
    "            cur_m = 0\n",
    "            for index in range(1, n):\n",
    "                cur_offset = position[index]\n",
    "                cur_force += cur_offset\n",
    "                if cur_force>=target:\n",
    "                    cur_force = 0\n",
    "                    cur_m += 1\n",
    "                    if cur_m==m:\n",
    "                        return -1\n",
    "            return 1\n",
    "        import bisect\n",
    "        index = bisect.bisect_left(range(min_offset,all_sum), 0, key=calculate)\n",
    "\n",
    "        # for i in range(min_offset,all_sum):\n",
    "        #     print(i,calculate(i))\n",
    "        return index-1+min_offset\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position=sorted(position)\n",
    "        lo=1\n",
    "        hi=position[-1]-position[0]\n",
    "        ans=-1\n",
    "\n",
    "        def check(x,position1):\n",
    "            pre=position1[0]\n",
    "            cnt=1\n",
    "            for i in range(1,len(position1)):  # 判断以x为距离能够放几个球\n",
    "                if position1[i]-pre>=x:\n",
    "                    pre=position1[i]\n",
    "                    cnt+=1\n",
    "                # print(position1)\n",
    "                # if position1[i] -position1[i-1] >= x:\n",
    "                #     print(position1[i],position1[i-1])\n",
    "                #     pre = position1[i]\n",
    "                #     cnt += 1\n",
    "            return cnt>=m\n",
    "\n",
    "\n",
    "        while lo<=hi:\n",
    "            mid=lo+(hi-lo)//2\n",
    "            if check(mid,position):\n",
    "                ans=mid\n",
    "                lo=mid+1\n",
    "            else:\n",
    "                hi=mid-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        n = len(position)\n",
    "        lo = 1\n",
    "        hi = position[-1] - position[0]\n",
    "        ans = 0\n",
    "        while lo <= hi:\n",
    "            mid = (lo+hi) // 2\n",
    "            prev, count = position[0], 1\n",
    "            for i in range(1,n):\n",
    "                if position[i] - prev >= mid:\n",
    "                    count += 1\n",
    "                    prev = position[i]\n",
    "                    if count > m: break\n",
    "            if count < m: \n",
    "                hi = mid-1\n",
    "            else:\n",
    "                ans = mid \n",
    "                lo = mid+1\n",
    "        return ans\n",
    "\n",
    "            \n",
    "                       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # 乍一看像贪心\n",
    "        # 实则这种最小最大,可以用二分答案\n",
    "        # 最小磁力=t,如果t能放入>=m个球\n",
    "        # 那t-1,t-2必然也可以\n",
    "        # 使得check函数成立(能放m个球)的最大t\n",
    "        position.sort()\n",
    "        def check(t):\n",
    "            count = 1\n",
    "            cur_num = position[0]\n",
    "            for i, p in enumerate(position):\n",
    "                if p - cur_num >= t:\n",
    "                    count += 1\n",
    "                    cur_num = position[i]\n",
    "            return count >= m\n",
    "             \n",
    "        # 二分查找能使得check成立的最大的t \n",
    "        l, r = 1, position[-1] - position[0]\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxDistance(self, position, m):\n",
    "\t\tposition.sort()\n",
    "\t\treturn self.bs(position, m, 1, position[-1] - position[0])\n",
    "\t\n",
    "\tdef bs(self, position, m, l, r):\n",
    "\t\tif l > r:\n",
    "\t\t\treturn r\n",
    "\t\tmid = (l + r) // 2\n",
    "\t\tif self.chk(position, m, mid):\n",
    "\t\t\treturn self.bs(position, m, mid + 1, r)\n",
    "\t\telse:\n",
    "\t\t\treturn self.bs(position, m, l, mid - 1)\n",
    "\t\n",
    "\tdef chk(self, position, m, d):\n",
    "\t\tcur = 1\n",
    "\t\tlast = position[0]\n",
    "\t\tfor p in position:\n",
    "\t\t\tif p - last >= d:\n",
    "\t\t\t\tcur += 1\n",
    "\t\t\t\tif cur == m:\n",
    "\t\t\t\t\treturn True\n",
    "\t\t\t\tlast = p\n",
    "\t\treturn False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def count(x: int) -> int: # 球间距（磁力) 为x，返回可以放下球的个数\n",
    "            pre = position[0] # 初始化第一个球的位置\n",
    "            cnt = 1 # 统计可以放下球的个数\n",
    "            for i in range(1, len(position)): # 迭代下一个球可以放的位置，\n",
    "                if position[i] - pre >= x: # 累计可以放下球的个数\n",
    "                    pre = position[i]\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        position.sort() # 排序，方便二分查找\n",
    "        left, right, ans = 1, (position[-1] - position[0]) // (m - 1), -1\n",
    "        while left < right: # 闭区间二分查找，循环结束条件:区间为空\n",
    "            mid = (left + right + 1) // 2\n",
    "            if count(mid) < m: # 如果不能放下m个球，减少球间距x\n",
    "                right = mid - 1\n",
    "            else: # 如果可以放下m个球，增大球间距x \n",
    "                left = mid\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(ans):\n",
    "            pre = position[0]\n",
    "            cnt = 1\n",
    "            for i in range(1,len(position)):\n",
    "                if position[i]-pre >= ans:\n",
    "                    pre = position[i]\n",
    "                    cnt +=1\n",
    "            return cnt >=m\n",
    "\n",
    "        position.sort()\n",
    "\n",
    "        left,right,ans = 1, position[-1]-position[0],-1\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid +1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        n = len(position)\n",
    "\n",
    "        def check(x: int) -> bool:\n",
    "            prev = position[0]\n",
    "            cnt = 1\n",
    "            for i in range(1, n):\n",
    "                if position[i] >= prev + x:\n",
    "                    prev = position[i]\n",
    "                    cnt += 1\n",
    "            return cnt >= m\n",
    "\n",
    "        # Upper bound.\n",
    "        left, right = 0, position[-1]\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        def ck(x):\n",
    "            cnt, pre = 1, position[0] \n",
    "            for i in range(1, len(position)): \n",
    "                if position[i] - pre >= x: \n",
    "                    pre = position[i]\n",
    "                    cnt += 1 \n",
    "            return cnt >= m\n",
    "        l, r = 1, (position[-1] - position[0]) // (m - 1)\n",
    "        while l < r: \n",
    "            mid = l + r + 1 >> 1 \n",
    "            if ck(mid): l = mid \n",
    "            else: r = mid - 1 \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        def checkit(k):\n",
    "            cnt = 1\n",
    "            pre = position[0]\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - pre >= k:\n",
    "                    cnt += 1\n",
    "                    pre = position[i]\n",
    "            return cnt >= m\n",
    "        \n",
    "        low, high = 0, position[-1]\n",
    "        while low <= high:\n",
    "            mid = low + high >> 1\n",
    "            # pd = checkit(mid)\n",
    "            if checkit(mid):\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # 磁力 x 会随球的数量 m 的增加而减少，因此是满足单调性的\n",
    "        position.sort()\n",
    "        n = len(position)\n",
    "        def check(x:int)->bool:\n",
    "            cnt = 1\n",
    "            pre = position[0]\n",
    "            for i in range(1, n):\n",
    "                if position[i] - pre >= x:\n",
    "                    cnt += 1\n",
    "                    pre = position[i]\n",
    "            return cnt >= m\n",
    "\n",
    "        l, r = 1, position[-1]\n",
    "        while l < r:\n",
    "            x = (l+r+1)//2\n",
    "            if check(x):\n",
    "                l = x\n",
    "            else:\n",
    "                r = x-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def cn(x):\n",
    "            pre=0\n",
    "            cont=1\n",
    "            for i in range(1,len(position)):\n",
    "                if position[i] - position[pre] >= x:\n",
    "                    cont+=1\n",
    "                    pre=i\n",
    "            return cont>=m\n",
    "        position.sort()\n",
    "        left=1\n",
    "        right=position[-1]-position[0]\n",
    "        while left <=right:\n",
    "            mid=left+(right-left)//2\n",
    "            if cn(mid):\n",
    "                \n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return right\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "\n",
    "        def check(x: int) -> bool:\n",
    "            pre = position[0]\n",
    "            cnt = 1\n",
    "            for i, v in enumerate(position):\n",
    "                if v - pre >= x:\n",
    "                    pre = v\n",
    "                    cnt += 1\n",
    "                    if cnt >= m:\n",
    "                        return True\n",
    "            return cnt >= m\n",
    "\n",
    "        lo, hi = 1, position[-1] - position[0]\n",
    "        while lo < hi:\n",
    "            mid = lo + hi + 1 >> 1\n",
    "            if check(mid):\n",
    "                lo = mid\n",
    "            else:\n",
    "                hi = mid - 1\n",
    "        return lo\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, pos: List[int], m: int) -> int:\n",
    "        pos.sort()\n",
    "        n = len(pos)\n",
    "\n",
    "        def check(x, m):  # 当最大距离为x的时候，是否合适？\n",
    "            pre = right = 0  # 第一个选pre\n",
    "            while m:\n",
    "                while right < n and pos[right] - pos[pre] < x:\n",
    "                    right += 1\n",
    "                if right == n:\n",
    "                    return False\n",
    "                pre = right\n",
    "                m -= 1\n",
    "\n",
    "            return True\n",
    "\n",
    "        left, right = 1, pos[-1] - pos[0]\n",
    "        while left <= right:  # 左边的一定可以\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid, m - 1):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return right if check(right, m - 1) else left\n",
    "        # print(left, right)\n",
    "\n",
    "\n",
    "pos = [5,4,3,2,1,1000000000]\n",
    "m = 2\n",
    "c = Solution()\n",
    "print(c.maxDistance(pos, m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # looking for max(f) intervals that can put n balls, that n <= m\n",
    "        position.sort()\n",
    "        l, r = 0, position[-1] - position[0] + 1\n",
    "        while l < r:\n",
    "            mid = l + r + 1>> 1\n",
    "            cnt = 1\n",
    "            start = position[0]\n",
    "            for num in position:\n",
    "                if mid + start <= num:\n",
    "                    start = num\n",
    "                    cnt += 1\n",
    "            print(mid, cnt)\n",
    "            if cnt < m:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "\n",
    "        def check(dis):\n",
    "            cnt = 1\n",
    "            pre = position[0]\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i]-pre >= dis:\n",
    "                    pre = position[i]\n",
    "                    cnt += 1\n",
    "            return cnt >= m\n",
    "\n",
    "        position.sort()\n",
    "        left, right, ans = 1, position[-1] - position[0], 1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        def check(x):\n",
    "            # 第一个球放在position[0]，第二个球至少放在position[0]+x，所以需要找到第一个position【i]>=position[i-1]+x,最后观察放的球数是否超过m,return True,return False\n",
    "            pre=position[0]\n",
    "            cnt=1\n",
    "            for i in range(1,len(position)):\n",
    "                if position[i]>=pre+x:\n",
    "                    cnt+=1\n",
    "                    pre=position[i]\n",
    "            return cnt>=m\n",
    "\n",
    "        l,r=1,position[-1]-position[0]\n",
    "        while l<r:\n",
    "            mid=l+r+1>>1\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "对于长度为n的position数组，有n-1个相邻的段\n",
    "由于磁力的定义是|x - y|，也就是相邻段的长度\n",
    "我们定义一个判断函数f(m, T)，判断Position数组里是否有存在\n",
    "至少 m-1 个长度 >= T 的段\n",
    "T越大，条件越难满足；T越小，条件越容易满足\n",
    "因此我们动态变化T，二分地去找答案，找到最大的那个满足条件的T\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        if m == 2:\n",
    "            return max(position) - min(position)\n",
    "        position.sort()\n",
    "        left, right = 1, position[-1] - position[0]\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if self.check(position, m, mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "        \n",
    "    # 在position中找m个点使得m个点之间的距离都 >= T\n",
    "    def check(self, position, m, t):\n",
    "        count = 0\n",
    "        pre = position[0]\n",
    "        for i in range(1, len(position)):\n",
    "            if position[i] - pre >= t:\n",
    "                count += 1\n",
    "                pre = position[i]\n",
    "        return count >= m - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        n = len(position)\n",
    "        position.sort()\n",
    "\n",
    "        low, high = 1, position[n - 1] - position[0] + 1\n",
    "        while low < high:\n",
    "            mid = low + high >> 1\n",
    "            cnt, val = 0, 1\n",
    "            for i in range(1, n, 1):\n",
    "                cnt += position[i] - position[i - 1]\n",
    "                if cnt >= mid:\n",
    "                    val += 1\n",
    "                    cnt = 0\n",
    "            if val >= m: low = mid + 1\n",
    "            else: high = mid\n",
    "        return low - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        left, right = 1, position[-1] - position[0] + 1\n",
    "        while left < right:\n",
    "            cnt, pres, mid = 1, position[0], (left + right) // 2\n",
    "            for x in position[1:]:\n",
    "                if pres + mid <= x:\n",
    "                    pres = x\n",
    "                    cnt += 1\n",
    "            if cnt < m:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "最小磁力越大，能放置的球越少，具备单调性，抽象为二分搜索\n",
    "设最小磁力为x，区间为[1, position[-1] - position[0]]，在这个区间内，通过二分搜索找到能够放置的球\n",
    "不大于m个\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # 判断最小磁力为x时，能放置的球数m'\n",
    "        def find(x: int) -> int:\n",
    "            cnt = 1 # 只有一个球\n",
    "            base_pos = position[0]\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - base_pos >= x:\n",
    "                    cnt += 1\n",
    "                    base_pos = position[i]\n",
    "            return cnt\n",
    "\n",
    "        position.sort()\n",
    "        left, right = 1, position[-1] - position[0] + 1\n",
    "        while left < right:\n",
    "            x = left + (right - left) // 2\n",
    "            y = find(x)\n",
    "            if y >= m:\n",
    "                left = x + 1\n",
    "            else:\n",
    "                right = x\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        if len(position) < m:\n",
    "            return 0\n",
    "        max_diff = (position[-1] - position[0]) // (m-1)\n",
    "        min_diff = min([position[i+1] - position[i] for i in range(len(position) - 1)])\n",
    "\n",
    "        def check(diff):\n",
    "            tmp = 1\n",
    "            last_position = position[0]\n",
    "            for i in position[1:]:\n",
    "                if i - last_position >= diff:\n",
    "                    tmp += 1\n",
    "                    last_position = i\n",
    "            # print(diff, tmp)\n",
    "            if tmp >= m:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        while min_diff < max_diff:\n",
    "            # print(min_diff, max_diff)\n",
    "            mid_diff = (max_diff + min_diff + 1) // 2\n",
    "            if check(mid_diff):\n",
    "                min_diff = mid_diff\n",
    "            else:\n",
    "                max_diff = mid_diff - 1\n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # looking for max(f) intervals that can put m balls\n",
    "        position.sort()\n",
    "        l, r = 0, (position[-1] - position[0])//(m - 1)\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            cnt = 1\n",
    "            start = position[0]\n",
    "            for num in position:\n",
    "                if mid + start <= num:\n",
    "                    start = num\n",
    "                    cnt += 1\n",
    "            if cnt >= m:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l-1\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # looking for max(f) intervals that can put m balls\n",
    "        position.sort()\n",
    "        l, r = 0, (position[-1] - position[0])//(m - 1)\n",
    "        while l < r:\n",
    "            mid = l + r + 1>> 1\n",
    "            cnt = 1\n",
    "            start = position[0]\n",
    "            for num in position:\n",
    "                if mid + start <= num:\n",
    "                    start = num\n",
    "                    cnt += 1\n",
    "            if cnt < m:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        left = 1\n",
    "        right = (position[-1]-position[0])//(m-1)\n",
    "        while left<right:\n",
    "            mid = (left+right+1)>>1\n",
    "            count = 0\n",
    "            flag = -inf\n",
    "            for i in position:\n",
    "                if i>=flag+mid:\n",
    "                    count+=1\n",
    "                    flag=i\n",
    "            if count>=m:\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        left, right = 0, position[-1] - position[0]\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            cnt = 1\n",
    "            i, j = 0, 1\n",
    "            while j < len(position):\n",
    "                if position[j] - position[i] >= mid:\n",
    "                    cnt += 1\n",
    "                    i = j\n",
    "                    j = j + 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            if cnt >= m:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        left = 0\n",
    "        right = position[-1] - position[0]\n",
    "        while left < right:\n",
    "            mid = (right - left + 1) // 2 + left\n",
    "            if self.check(position, m, mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "    \n",
    "    def check(self, position, m, mid):\n",
    "        cnt = 0\n",
    "        pre = position[0]\n",
    "        for now in position:\n",
    "            if now - pre >= mid:\n",
    "                cnt += 1\n",
    "                pre = now\n",
    "        return cnt >= m - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(target):\n",
    "            value = 0\n",
    "            l = position[0]\n",
    "            for i in range(1,len(position)):\n",
    "\n",
    "                if position[i] - l >= target:\n",
    "                    value += 1\n",
    "                    l = position[i]\n",
    "\n",
    "            if value >= (m-1):\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        position.sort()\n",
    "        left,right = 0 ,position[-1]-position[0]\n",
    "        res =-1\n",
    "        while left <= right:\n",
    "            mid = (right +left) //(2)\n",
    "            if check(mid):\n",
    "                res = mid\n",
    "\n",
    "                left =mid +1\n",
    "                \n",
    "            else:\n",
    "                right = mid-1\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxDistance(self, position: List[int], m: int) -> int:\n",
    "#         left = 0\n",
    "#         position.sort()\n",
    "#         right = (position[-1]-position[0])//(m-1)\n",
    "\n",
    "#         def check(mid):\n",
    "#             count = 1\n",
    "#             pre = position[0]\n",
    "#             i = 1\n",
    "#             n= len(position)\n",
    "#             while i<n:\n",
    "#                 if position[i] >=pre+mid:\n",
    "#                     count+=1\n",
    "#                     pre = position[i]\n",
    "#                 i+=1\n",
    "#             return count>m\n",
    "\n",
    "#         while left<right:\n",
    "#             mid = left+(right-left)//2\n",
    "#             if check(mid):\n",
    "#                 left = mid+1\n",
    "#             else:\n",
    "#                 right = mid\n",
    "#         return left  \n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # 对position进行排序\n",
    "        position.sort()\n",
    "        # 初始化可能的答案的左右边界，最小为1，最大为整个长度除以m-1\n",
    "        left = 1\n",
    "        right = (position[-1]-position[0])//(m-1)\n",
    "        n = len(position)\n",
    "        # check函数返回对于最小磁力为x，是否可以成功\n",
    "        def check(x):\n",
    "            # 将position[0]作为第一个放球位置，count计数，pre表示上一个放球位置\n",
    "            count = 1\n",
    "            pre = position[0]\n",
    "            i = 1\n",
    "            while i < n:\n",
    "                # 如果此时position[i]位置与上一个放球位置之间磁力大于等于x，\n",
    "                # count++，更新pre\n",
    "                if position[i] >= pre + x:\n",
    "                    count += 1\n",
    "                    pre = position[i]\n",
    "                i += 1\n",
    "            # 最后看放球的个数是否大于等于m\n",
    "            return count >= m\n",
    "        # 二分查找阶段，找到满足条件的最大值\n",
    "        while left < right:\n",
    "            mid = left + (right-left+1)//2\n",
    "            # 如果mid满足，那么mid作为下一个left\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            # mid不满足，说明答案肯定在mid左边\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            pre = position[0]\n",
    "            cnt = 1\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - pre >= x:\n",
    "                    pre = position[i]\n",
    "                    cnt += 1\n",
    "            return cnt >= m\n",
    "\n",
    "        position.sort()\n",
    "        left, right, ans = 1, position[-1] - position[0], -1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2;\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(target):\n",
    "            value = 0\n",
    "            l = position[0]\n",
    "            for i in range(1,len(position)):\n",
    "\n",
    "                if position[i] - l >= target:\n",
    "                    value += 1\n",
    "                    l = position[i]\n",
    "\n",
    "            return value >= (m-1)\n",
    "                \n",
    "        position.sort()\n",
    "        left,right = 1 ,position[-1]-position[0]+1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (right +left) //(2)\n",
    "            if check(mid):\n",
    "\n",
    "                left =mid +1\n",
    "                \n",
    "            else:\n",
    "                right = mid -1\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(self, position: List[int], m: int, mid: int):\n",
    "            sum = 0\n",
    "            pre = position[0]\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - pre >= mid:\n",
    "                    sum += 1\n",
    "                    pre = position[i]\n",
    "                    if sum + 1 >= m:\n",
    "                        return True\n",
    "            return sum >= m\n",
    "\n",
    "        position.sort()\n",
    "        # 范围为 (0, position[-1] - position[0] + 1)\n",
    "        l = 0\n",
    "        r = position[-1] - position[0] + 1\n",
    "\n",
    "        while l + 1 < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(self, position, m, mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(dis: int) -> bool:\n",
    "            count, pre = 1, 0\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - position[pre] >= dis:\n",
    "                    pre = i\n",
    "                    count += 1\n",
    "                    if count >= m:\n",
    "                        return True\n",
    "            \n",
    "            return False\n",
    "\n",
    "        position.sort()\n",
    "        left, right = 1, (position[-1] - position[0]) // (m - 1) + 1\n",
    "        res = 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) //2\n",
    "            if check(mid):\n",
    "                res = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(x):\n",
    "            pre = position[0]\n",
    "            cnt = 1\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - pre >= x:\n",
    "                    pre = position[i]\n",
    "                    cnt += 1\n",
    "            return cnt >= m \n",
    "        position.sort()\n",
    "        left = 1\n",
    "        right = position[-1] - position[0]\n",
    "        res = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                res = mid \n",
    "                left = mid + 1\n",
    "                \n",
    "            else:\n",
    "                right = mid - 1\n",
    "                \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "\n",
    "        def check(x):\n",
    "            cnt, pre = 1, position[0]\n",
    "            for i in range(1,len(position)):\n",
    "                if position[i] - pre >= x:\n",
    "                    cnt += 1\n",
    "                    pre = position[i]\n",
    "            \n",
    "            return cnt >= m\n",
    "\n",
    "        # https://github.com/python/cpython/blob/main/Lib/bisect.py\n",
    "        lo = 1\n",
    "        hi = position[-1] - position[0] + 1\n",
    "        ans = 1\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if check(mid):      #\n",
    "                ans = mid       # 如果cnt>=m, mid就是答案\n",
    "                lo = mid + 1    # 所以lo可以置为 mid + 1。\n",
    "            else:\n",
    "                hi = mid\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        n = len(position)\n",
    "        position.sort()\n",
    "\n",
    "        def check(k):\n",
    "            remain = m - 1\n",
    "            last = position[0]\n",
    "            while remain>0:\n",
    "                idx = bisect_left(position, last+k)\n",
    "                if not idx<=n-remain:\n",
    "                    return False\n",
    "                last = position[idx]\n",
    "                remain -= 1\n",
    "            return True\n",
    "\n",
    "        l,r = 1,max(position)\n",
    "        ans = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # 每个球的间距一样的情况下，如何使间距最大\n",
    "        def check(x):  # 在保证间距大于等于x的情况下，能否至少放m个球\n",
    "            pre = position[0]\n",
    "            cnt = 1\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - pre >= x:\n",
    "                    cnt += 1\n",
    "                    pre = position[i]\n",
    "            return cnt >= m\n",
    "\n",
    "        position.sort()\n",
    "        ans = -1\n",
    "        left = 1\n",
    "        right = position[-1] - position[0]\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        if check(left):\n",
    "            ans = left\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "\n",
    "        def check(flag):\n",
    "            num = m-1\n",
    "            lastOne = position[0]\n",
    "            for p in position:\n",
    "                # print('p',p,'last',lastOne)\n",
    "                if p-lastOne>=flag:\n",
    "                    lastOne=p\n",
    "                    num=num-1\n",
    "                    if num==0:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        left,right = 1,position[-1]-position[0]\n",
    "        # print('left',left,'right',right)\n",
    "        while right >= left:\n",
    "            mid = (right+left)//2\n",
    "            # print('mid',mid)\n",
    "            if check(mid):\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1    \n",
    "        return right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(x):\n",
    "            pre=position[0]\n",
    "            cnt=1\n",
    "            for i in range(1,len(position)):\n",
    "                if position[i]-pre>=x:\n",
    "                    pre=position[i]\n",
    "                    cnt+=1\n",
    "            return cnt>=m\n",
    "\n",
    "        position.sort()\n",
    "        left,right,ans=1,position[-1]-position[0],-1\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                ans=mid\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "\n",
    "        def check(mid:int) -> bool:\n",
    "            cnt = 1\n",
    "            pre = position[0]\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - pre >= mid:\n",
    "                    pre = position[i]\n",
    "                    cnt += 1\n",
    "            return cnt >= m\n",
    "        \n",
    "        position.sort()\n",
    "        l, r, ans= 1, position[-1] - position[0], -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judge(self, force, in_list, m):\n",
    "        in_list.sort()\n",
    "        stack = []\n",
    "        for i in in_list:\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "                m -= 1\n",
    "                if m == 0:\n",
    "                    return True\n",
    "            else:\n",
    "                if stack and i - stack[-1] < force:\n",
    "                    pass\n",
    "                else:\n",
    "                    stack.append(i)\n",
    "                    m -= 1\n",
    "                    if m == 0:\n",
    "                        return True\n",
    "        if m == 0:\n",
    "            return True\n",
    "        else:    \n",
    "            return False        \n",
    "                  \n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        left = 1 - 1\n",
    "        right = max(position) - min(position) + 1\n",
    "        while left + 1 != right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.judge(mid, position, m):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "\n",
    "        def check(f):\n",
    "            pre = position[0]\n",
    "            cnt = 1\n",
    "            for pos in position[1:]:\n",
    "                if pos - pre >= f:\n",
    "                    cnt += 1\n",
    "                    pre = pos\n",
    "            return cnt >= m\n",
    "\n",
    "        left, right = 1, position[-1]\n",
    "        while left <= right:\n",
    "            mid = (left + right ) >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(x):\n",
    "            count,pre=0,-inf\n",
    "            for pos in position:\n",
    "                if pos-pre>=x:\n",
    "                    count+=1\n",
    "                    pre=pos\n",
    "                    if count==m:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        position.sort()\n",
    "        left,right=1,(position[-1]-position[0])//(m-1)+1\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return left-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        \n",
    "        def check(x):\n",
    "            pre = position[0]\n",
    "            count = 1\n",
    "            for i in range(1, len(position)):\n",
    "                if position[i] - pre >= x:\n",
    "                    count += 1\n",
    "                    pre = position[i]\n",
    "            return count >= m\n",
    "\n",
    "        position.sort()\n",
    "        left, right = 1, position[-1] - position[0]\n",
    "        # result = -1\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            print(left, right)\n",
    "            if check(mid) is False:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        # 对position进行排序\n",
    "        position.sort()\n",
    "        # 初始化可能的答案的左右边界，最小为1，最大为整个长度除以m-1\n",
    "        left = 1\n",
    "        right = (position[-1]-position[0])//(m-1)\n",
    "        n = len(position)\n",
    "        # check函数返回对于最小磁力为x，是否可以成功\n",
    "        def check(x):\n",
    "            # 将position[0]作为第一个放球位置，count计数，pre表示上一个放球位置\n",
    "            count = 1\n",
    "            pre = position[0]\n",
    "            i = 1\n",
    "            while i < n:\n",
    "                # 如果此时position[i]位置与上一个放球位置之间磁力大于等于x，\n",
    "                # count++，更新pre\n",
    "                if position[i] >= pre + x:\n",
    "                    count += 1\n",
    "                    pre = position[i]\n",
    "                i += 1\n",
    "            # 最后看放球的个数是否大于等于m\n",
    "            return count >= m\n",
    "        # 二分查找阶段，找到满足条件的最大值\n",
    "        while left < right:\n",
    "            mid = left + (right-left+1)//2\n",
    "            # 如果mid满足，那么mid作为下一个left\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            # mid不满足，说明答案肯定在mid左边\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        def check(f):\n",
    "            pre=position[0]\n",
    "            cnt=1\n",
    "            for p in position[1:]:\n",
    "                if p-pre>=f:\n",
    "                    cnt+=1\n",
    "                    pre=p\n",
    "\n",
    "            return cnt>=m\n",
    "        left,right = 0,position[-1]-position[0]\n",
    "        while left <=right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "\n",
    "        def check(f):\n",
    "            pre = position[0]\n",
    "            cnt = 1\n",
    "            for pos in position[1:]:\n",
    "                if pos - pre >= f:\n",
    "                    cnt += 1\n",
    "                    pre = pos\n",
    "            return cnt >= m\n",
    "\n",
    "        left, right = 1, position[-1]\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        def check(x, pos, m):\n",
    "            lastPos = pos[0]\n",
    "            m-=1\n",
    "            for i in pos:\n",
    "                if i-lastPos>=x:\n",
    "                    m-=1\n",
    "                    lastPos = i\n",
    "                if m==0:\n",
    "                    break\n",
    "            return m==0\n",
    "\n",
    "        position.sort()\n",
    "        # 最大间隔\n",
    "        end = position[-1] - position[0]\n",
    "        # 最小间隔\n",
    "        start = end\n",
    "        for i in range(len(position)-1):\n",
    "            if position[i+1]-position[i]<start:\n",
    "                start = position[i+1]-position[i]\n",
    "        end = end//(m-1)\n",
    "        while start+1<end:\n",
    "            mid = (start+end)//2\n",
    "            if check(mid,position,m):\n",
    "                start=mid\n",
    "            else:\n",
    "                end = mid\n",
    "        if check(end, position,m):\n",
    "            return(end)\n",
    "        elif check(start, position, m):\n",
    "            return(start)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, position: List[int], m: int) -> int:\n",
    "        position.sort()\n",
    "        l,r = 1,position[-1]\n",
    "\n",
    "        def check(f):\n",
    "            pre = position[0]\n",
    "            cnt = 1\n",
    "            for p in position[1:]:\n",
    "                if p-pre >=f:\n",
    "                    cnt+=1\n",
    "                    pre = p \n",
    "            return cnt>=m \n",
    "\n",
    "        while l<r:\n",
    "            mid = (r+l+1) >>1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return l"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
